package org.liaohailong.helloworld.practicemiddle;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * Author: liaohailong
 * Time: 2021/6/29 11:48
 * Describe: 中级算法 - 数字和字符串
 */
public class ArrayStringPractice {

    // LC 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 2) return new LinkedList<>();

        // 排序方便去重复
        Arrays.sort(nums);
        LinkedList<List<Integer>> result = new LinkedList<>();

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) continue;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                } else {
                    LinkedList<Integer> list = new LinkedList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                    // 可能还有，继续找
                    left++;
                    right--;
                    // 重复的不检查
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
        }
        return result;
    }

    // LC 无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int i = 0, j = -1;
        int max = j - i + 1;
        for (int k = 0; k < chars.length; k++) {
            int index = indexOf(chars, i, j, chars[k]);
            // 未发现重复，延长i,j
            if (index == -1) {
                j = k;
                max = Math.max(max, j - i + 1);
            }
            // 发现重复，滑动i,j
            else {
                j = k;
                i = index + 1;
                max = Math.max(max, j - i + 1);
            }
        }
        return max;
    }

    private int indexOf(char[] chars, int i, int j, char c) {
        for (int k = i; k <= j; k++) {
            if (chars[k] == c) return k;
        }
        return -1;
    }

    // LC 矩阵置零
    public void setZeroes(int[][] matrix) {
        boolean[] rows = new boolean[matrix.length];
        boolean[] columns = new boolean[matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    rows[i] = true;
                    columns[j] = true;
                }
            }
        }

        for (int i = 0; i < rows.length; i++) {
            if (rows[i]) {
                Arrays.fill(matrix[i], 0);
            }
        }

        for (int j = 0; j < columns.length; j++) {
            if (columns[j]) {
                for (int i = 0; i < matrix.length; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    // LC 字母异位词分组
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            List<String> list = map.get(key);
            if (list == null) {
                list = new LinkedList<>();
            }
            list.add(str);
            map.put(key, list);
        }
        List<List<String>> RESULT = new LinkedList<>();
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            List<String> value = entry.getValue();
            RESULT.add(value);
        }
        return RESULT;
    }

    // LC 最长回文子串
    public String longestPalindrome(String s) {
        if (s.length() < 1) return s;

        char[] chars = s.toCharArray();
        int N = chars.length;

        int[] max = new int[2];//[0] start [1] end

        int[] temp1 = new int[2];//[0] start [1] end
        int[] temp2 = new int[2];//[0] start [1] end
        int[] temp3 = new int[2];//[0] start [1] end
        for (int i = 0; i < N; i++) {
            _longestPalindrome(chars, i, i, temp1);
            _longestPalindrome(chars, i, i + 1, temp2);

            if (temp1[1] - temp1[0] >= temp2[1] - temp2[0]) {
                temp3[0] = temp1[0];
                temp3[1] = temp1[1];
            } else {
                temp3[0] = temp2[0];
                temp3[1] = temp2[1];
            }

            // find new max
            if (temp3[1] - temp3[0] > max[1] - max[0]) {
                max[0] = temp3[0];
                max[1] = temp3[1];
            }
        }

        return s.substring(max[0], max[1] + 1);
    }

    private void _longestPalindrome(char[] chars, int i, int j, int[] res) {
        int start = i, end = j;
        while (start >= 0 && end <= chars.length - 1) {
            if (chars[start] == chars[end]) {
                res[0] = start;
                res[1] = end;
                start--;
                end++;
            } else break;
        }
    }

    // LC 递增的三元子序列
//    public boolean increasingTriplet(int[] nums) {
//        if (nums.length < 3) return false;
//
//        for (int i = 0; i < nums.length - 2; i++) {
//            LinkedList<Integer> values = new LinkedList<>();
//            for (int j = i + 1; j < nums.length; j++) {
//                if (nums[i] < nums[j]) values.add(nums[j]);
//            }
//
//            int curr = nums[i];
//            int count = 1;
//            for (Integer value : values) {
//                if (value > curr) {
//                    count++;
//                    curr = value;
//                    if (count >= 3) return true;
//                } else {
//                    curr = Math.min(curr, value);
//                    count = 2;
//                }
//            }
//        }
//
//        return false;
//    }

    // LC 递增的三元子序列
    public boolean increasingTriplet(int[] nums) {
        int len = nums.length;
        if (len < 3) return false;
        // min保存最小值,temp保存大于最小值的较小值
        int min = nums[0], temp = Integer.MAX_VALUE;
        for (int i = 1; i < len; i++) {
            if (nums[i] <= min) {
                min = nums[i]; // 跟新最小值
            } else if (nums[i] > temp) {
                return true;
            } else {
                temp = nums[i];
            }
        }
        return false;
    }

}
